package C048;

/**
 * ClassName: C02
 * Package: C048
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/15 12:35
 * @Version 1.0
 * @Since 1.0
 */
public class C02 {
    public static void main(String[] args) {
        int[][] arr = {{1,1,1},{1,0,1},{1,1,1}};
        System.out.println(largest1BorderedSquare(arr));
    }

    public static int largest1BorderedSquare(int[][] arr) {
        changeSum(arr);

        if(getSum(arr, 0, 0, arr.length - 1, arr[0].length - 1) == 0) {
            return 0;
        }
        int ans = 1;
        int n = arr.length;
        int m = arr[0].length;
        // 遍历数组
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                for (int r1 = i, c1 = j, r2 = i + ans, c2 = j + ans, k = ans + 1;
                     r2 < n && c2 < m;
                     r2 ++, c2 ++, k ++){
                    if(getSum(arr, r1,c1,r2,c2) - getSum(arr, r1 + 1, c1 + 1, r2 - 1, c2 - 1) == (k - 1) << 2) {
                        ans = k;
                    }
                }
            }
        }

        return ans * ans;
    }

    private static int getSum(int[][] arr, int r1, int c1, int r2, int c2) {
        r1--;
        c1--;
        return get(arr, r2, c2) - get(arr, r2, c1) - get(arr, r1, c2) + get(arr, r1, c1);
    }

    private static void changeSum(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                arr[i][j] = get(arr, i, j) + get(arr, i, j - 1) + get(arr, i - 1, j) - get(arr, i - 1, j - 1);
            }
        }
    }

    private static int get(int[][] arr, int i, int j) {
        return i < 0 || j < 0 ? 0 : arr[i][j];
    }

}
